#include"maxHeap.h"

template<class T>
void Swap(T& a, T& b)
{
	T temp = a;
	a = b;
	b = temp;
}

template<class T>
maxHeap<T>::maxHeap() :heap(arrayLength), heapSize(0)//fallibility
{
	heap.reserve(arrayLengthMax);
}

template<class T>
void maxHeap<T>::push(const T theElement)
{
	if ( heapSize == arrayLength - 1 )
	{
		heap.resize(arrayLength * 2);
		arrayLength *= 2;
	}

	if (heapSize == 0)
	{
		heap[heapSize] = theElement;//fallibility
		heapSize++;
		return;
	}

	heap[heapSize] = theElement;//fallibility
	int currentNode = ++heapSize;
	while (currentNode != 1 && heap[(currentNode - 1) / 2] < heap[currentNode - 1])//fallibility
	{
		Swap(heap[currentNode - 1], heap[(currentNode - 1) / 2]);
		currentNode /= 2;
	}
}

template<class T>
void maxHeap<T>::pop()
{
	if (heapSize == 1)
	{
		heapSize--;
		return;
	}
	int flag;
	for (int j = 0; 2 * j + 3 <= heapSize || 2 * j + 2 <= heapSize;)
	{
		if (heap[2 * j + 1] < heap[2 * j + 2] || 2 * j + 3 > heapSize)
		{
			heap[j] = heap[2 * j + 2];
			j = 2 * j + 2;
		}
		else
		{
			heap[j] = heap[2 * j + 1];
			j = 2 * j + 1;
		}
		flag = j;
	}
	if ( flag != heapSize - 1)
	heap[flag] = heap[heapSize - 1];
	heapSize--;
}

template<class T>
void maxHeap<T>::initialize(std::vector<T>& theHeap, int theSize)
{
	heapSize = theSize;
	while (heapSize >= arrayLength - 1)
	{
		heap.resize(arrayLength * 2);
		arrayLength *= 2;
	}
	for (int i = 0; i < theHeap.size(); i++)
	{
		heap[i] = theHeap[i];
	}
	for (int root = heapSize / 2 - 1; root >= 0; --root)
	{
		T rootElement = heap[root];
		int child = ( root + 1 ) * 2 - 1;
		while (child + 1<= heapSize)
		{
			if (child + 1 < heapSize && heap[child] < heap[child + 1])
				++child;
			if (heap[child] <= rootElement)
				break;
			heap[( child + 1 ) / 2 - 1] = heap[child];
			child = ( child + 1 ) * 2 - 1;
		}
		heap[( child + 1 ) / 2 - 1] = rootElement;
	}

}